class Solution:
    def wordBreak(self, s: str, wordDict):
        word_dic = set(wordDict)
        cache = {len(s): [""]}
        
        def stns_since(i):
            if i not in cache:
                cache[i] = []
                for j in range(i+1, len(s) +1):
                    if s[i:j] in word_dic:
                        for post in stns_since(j):
                            cache[i].append(s[i:j] + (" " if post else "") + post)
            return cache[i]
        
        return stns_since(0)


s = "aaaaaaaaaaaaaaaaaaaaaaa"
wordDict = ["a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa", "aaaaaaaaa", "aaaaaaaaaa"]

print(len(Solution().wordBreak(s,wordDict)))